/*
leetcode 205. 同构字符串
给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

 

示例 1:

输入：s = "egg", t = "add"
输出：true
示例 2：

输入：s = "foo", t = "bar"
输出：false
示例 3：

输入：s = "paper", t = "title"
输出：true
 

提示：


1 <= s.length <= 5 * 10^4
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成
*/

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

bool isIsomorphic(string s, string t) {
    //两个字符串长度不一样，直接返回 false
    if (s.length() != t.length()) return false;

   //使用两个哈希表来检查双向映射，确保一一对应的关系
    unordered_map<char, char> mapST; // 映射 s -> t
    unordered_map<char, char> mapTS; // 映射 t -> s

    for (int i = 0; i < s.length(); i++) {
        char sChar = s[i];
        char tChar = t[i];

        // 检查 s -> t 的映射是否一致
        //检查字符 sChar 是否已经在 mapST 中有记录
        if (mapST.count(sChar)) {
            //如果 mapST 中记录的 sChar 的映射值不是当前的 tChar，
            //说明映射冲突，两个字符串无法是同构的，直接返回 false
            if (mapST[sChar] != tChar) return false;
        } else {
            //如果 sChar 尚未在 mapST 中建立映射，就将当前的 sChar -> tChar 关系存入映射表中。
            mapST[sChar] = tChar;
        }

        // 检查 t -> s 的映射是否一致
        if (mapTS.count(tChar)) {
            if (mapTS[tChar] != sChar) return false;
        } else {
            mapTS[tChar] = sChar;
        }
    }

    return true;
}

int main() {
    string s = "egg";
    string t = "add";
    cout << (isIsomorphic(s, t) ? "true" : "false") << endl;

    s = "foo";
    t = "bar";
    cout << (isIsomorphic(s, t) ? "true" : "false") << endl;

    s = "paper";
    t = "title";
    cout << (isIsomorphic(s, t) ? "true" : "false") << endl;

    return 0;
}

/*
示例
输入：s = "egg", t = "add"

第一轮 (sChar = 'e', tChar = 'a')

mapST 为空，sChar = 'e' 不在 mapST 中。
建立映射：mapST['e'] = 'a'。
第二轮 (sChar = 'g', tChar = 'd')

sChar = 'g' 不在 mapST 中。
建立映射：mapST['g'] = 'd'。
第三轮 (sChar = 'g', tChar = 'd')

sChar = 'g' 在 mapST 中，且 mapST['g'] == 'd'，符合映射，继续。
返回 true，两个字符串是同构的。

反例
s = "foo", t = "bar"

第一轮 (sChar = 'f', tChar = 'b')

建立映射：mapST['f'] = 'b'。
第二轮 (sChar = 'o', tChar = 'a')

建立映射：mapST['o'] = 'a'。
第三轮 (sChar = 'o', tChar = 'r')

sChar = 'o' 在 mapST 中，但 mapST['o'] != 'r'。
返回 false。
*/

/*
哈希表：
哈希表是一种以键值对（key-value）形式存储数据的数据结构，它通过哈希函数将键映射到特定的位置（索引），从而实现高效的查找、插入和删除操作。

在 C++ 中，常用的哈希表容器是 std::unordered_map。

哈希表的特点
高效性：
哈希表的查找、插入和删除操作的平均时间复杂度是 O(1)。
这是通过哈希函数直接定位到元素所在的位置实现的。

非有序性：
哈希表中的元素存储顺序通常和插入顺序不同，具体取决于哈希函数。
如果需要有序的键值对，可以使用 std::map。

冲突处理：
当两个键经过哈希函数映射到相同的位置时，称为哈希冲突。
哈希表通过链地址法（链表）或开放地址法（探测）解决冲突。

#include <unordered_map>
#include <iostream>
using namespace std;

int main() {
    // 定义一个哈希表
    unordered_map<string, int> myMap;

    // 插入键值对
    myMap["apple"] = 5;
    myMap["banana"] = 3;
    myMap["cherry"] = 8;

    // 访问值
    cout << "apple: " << myMap["apple"] << endl; //输出 5

    // 查找键是否存在
    if (myMap.count("banana")) {
        cout << "banana exists, value: " << myMap["banana"] << endl; //存在，输出值为 3
    }

    // 删除键值对
    myMap.erase("cherry");

    // 遍历哈希表
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl; //输出 apple 和 banana 的键值对
    }

    return 0;
}

*/